SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Concurrent data structure</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Concurrent data structure</span></span>

</h1>

</header>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>concurrent data structure</b> (also called <b>shared data structure</b>) is a data structure designed for access and modification by multiple computing <a href="Thread_(computer_science)" class="mw-redirect" title="Thread (computer science)">threads</a> (or <a href="Process_(computing)" title="Process (computing)">processes</a> or nodes) on a computer, for example concurrent <a href="Message_queue" title="Message queue">queues</a>, concurrent <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stacks</a> etc. The concurrent data structure is typically considered to reside in an abstract storage environment known as shared memory, which may be physically implemented as either a tightly coupled or a distributed collection of storage modules. <sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Basic_principles">Basic principles</h2></div>

<p>Concurrent data structures, intended for use in

parallel or distributed computing environments, differ from

"sequential" data structures, intended for use on a uni-processor

machine, in several ways.<sup id="cite_ref-sahni_3-0" class="reference"><a href="#cite_note-sahni-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Most notably, in a sequential environment

one specifies the data structure's properties and checks that they

are implemented correctly, by providing <b>safety properties</b>. In

a concurrent environment, the specification must also describe

<b>liveness properties</b> which an implementation must provide.

Safety properties usually state that something bad never happens,

while liveness properties state that something good keeps happening.

These properties can be expressed, for example, using <a href="Linear_Temporal_Logic" class="mw-redirect" title="Linear Temporal Logic">Linear Temporal Logic</a>.

</p><p>The type of liveness requirements tend to define the data structure.

The <a href="Method_(computer_science)" class="mw-redirect" title="Method (computer science)">method</a> calls can be <a href="Blocking_(computing)" title="Blocking (computing)">blocking</a> or <a href="Non-blocking_algorithm" title="Non-blocking algorithm">non-blocking</a>. Data structures are not

restricted to one type or the other, and can allow combinations

where some method calls are blocking and others are non-blocking

(examples can be found in the <a href="Java_concurrency" title="Java concurrency">Java concurrency</a> software

library).

</p><p>The safety properties of concurrent data structures must capture their

behavior given the many possible interleavings of methods

called by different threads. It is quite

intuitive to specify how abstract data structures

behave in a sequential setting in which there are no interleavings.

Therefore, many mainstream approaches for arguing the safety properties of a

concurrent data structure (such as <a href="Serializability" class="mw-redirect" title="Serializability">serializability</a>, <a href="Linearizability" title="Linearizability">linearizability</a>, <a href="Sequential_consistency" title="Sequential consistency">sequential consistency</a>, and

quiescent consistency<sup id="cite_ref-sahni_3-1" class="reference"><a href="#cite_note-sahni-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>) specify the structures properties

sequentially, and map its concurrent executions to

a collection of sequential ones.

</p><p>To guarantee the safety and liveness properties, concurrent

data structures must typically (though not always) allow threads to

reach <a href="Consensus_(computer_science)" title="Consensus (computer science)">consensus</a> as to the results

of their simultaneous data access and modification requests. To

support such agreement, concurrent data structures are implemented

using special primitive synchronization operations (see <a href="Synchronization_(computer_science)#Hardware_synchronization" title="Synchronization (computer science)">synchronization primitives</a>)

available on modern <a href="Multiprocessing" title="Multiprocessing">multiprocessor machines</a>

that allow multiple threads to reach consensus. This consensus can be achieved in a blocking manner by using <a href="Spinlock" title="Spinlock">locks</a>, or without locks, in which case it is <a href="Non-blocking_algorithm" title="Non-blocking algorithm">non-blocking</a>. There is a wide body

of theory on the design of concurrent data structures (see

bibliographical references).

</p>

<div class="mw-heading mw-heading2"><h2 id="Design_and_implementation">Design and implementation</h2></div>

<p>Concurrent data structures are significantly more difficult to design

and to verify as being correct than their sequential counterparts.

</p><p>The primary source of this additional difficulty is concurrency, exacerbated by the fact that

threads must be thought of as being completely asynchronous:

they are subject to operating system preemption, page faults,

interrupts, and so on.

</p><p>On today's machines, the layout of processors and

memory, the layout of data in memory, the communication load on the

various elements of the multiprocessor architecture all influence performance.

Furthermore, there is a tension between correctness and performance: algorithmic enhancements that seek to improve performance often make it more difficult to design and verify a correct

data structure implementation.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>A key measure for performance is scalability, captured by the <a href="Speedup" title="Speedup">speedup</a> of the implementation. Speedup is a measure of how

effectively the application is using the machine it is running

on. On a machine with P processors, the speedup is the ratio of the structures execution time on a single processor to its execution time on P processors. Ideally, we want linear speedup: we would like to achieve a

speedup of P when using P processors. Data structures whose

speedup grows with P are called <b>scalable</b>. The extent to which one can scale the performance of a concurrent data structure is captured by a formula known as <a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a> and

more refined versions of it such as <a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a>.

</p><p>A key issue with the performance of concurrent data structures is the level of memory contention: the overhead in traffic to and from memory as a

result of multiple threads concurrently attempting to access the same

locations in memory. This issue is most acute with blocking implementations

in which locks control access to memory. In order to

acquire a lock, a thread must repeatedly attempt to modify that

location. On a <a href="Cache_coherence" title="Cache coherence">cache-coherent</a>

multiprocessor (one in which processors have

local caches that are updated by hardware to keep them

consistent with the latest values stored) this results in long

waiting times for each attempt to modify the location, and is

exacerbated by the additional memory traffic associated with

unsuccessful attempts to acquire the lock.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">ConcurrentDictionary</span>,<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> <span class="monospaced">ConcurrentQueue</span><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> and <span class="monospaced">ConcurrentStack</span><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> in the <span class="monospaced">System.Collections.Concurrent</span> namespace.

</p><p><span class="mw-default-size" typeof="mw:File"></span>

</p>

<p><a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a> instead wraps data structures in <span class="monospaced">Arc</span> and <span class="monospaced">Mutex</span>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-highlight mw-highlight-lang-rust mw-content-ltr" dir="ltr"><pre><span class="kd">let</span><span class="w"> </span><span class="n">counter</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Arc</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="n">Mutex</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="mi">0</span><span class="p">));</span>

</pre></div>

<ul><li><a href="Thread_safety" title="Thread safety">Thread safety</a></li>

<li><a href="Java_concurrency" title="Java concurrency">Java concurrency</a> (JSR 166)</li>

<li><a href="Java_ConcurrentMap" title="Java ConcurrentMap">Java ConcurrentMap</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDally2012" class="citation book cs1">Dally, J. W. (6 December 2012). <i>A VLSI Architecture for Concurrent Data Structures</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781461319955</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation book cs1"><i>23nd International Symposium on Distributed Computing, DISC</i>. Springer Science & Business Media. 2009.</cite></span>

</li>

<cite id="CITEREFMark_MoirNir_Shavit2007" class="citation book cs1">Mark Moir; <a href="Nir_Shavit" title="Nir Shavit">Nir Shavit</a> (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110401070433/http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf">"Concurrent Data Structures"</a> <span class="cs1-format">(PDF)</span>. In Dinesh Metha; <a href="Sartaj_Sahni" title="Sartaj Sahni">Sartaj Sahni</a> (eds.). <i>Handbook of Data Structures and Applications</i>. Chapman and Hall/CRC Press. pp. <span class="nowrap">47-14 –</span> <span class="nowrap">47-30</span>. Archived from <a rel="nofollow" class="external text" href="http://www.cs.tau.ac.il/~shanir/concurrent-data-structures.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 1 April 2011.</cite></span>

</li>

<cite id="CITEREFGramoli,_V.2015" class="citation conference cs1">Gramoli, V. (2015). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150410030004/http://sydney.edu.au/engineering/it/~gramoli/doc/pubs/gramoli-synchrobench.pdf">"More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. ACM. pp. <span class="nowrap">1–</span>10. Archived from <a rel="nofollow" class="external text" href="http://sydney.edu.au/engineering/it/~gramoli/doc/pubs/gramoli-synchrobench.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 10 April 2015.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2?view=net-9.0">"ConcurrentDictionary Class (System.Collections.Concurrent)"</a>. <i>learn.microsoft.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">26 November</span> 2024</span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentqueue-1?view=net-9.0">"ConcurrentQueue Class (System.Collections.Concurrent)"</a>. <i>learn.microsoft.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">26 November</span> 2024</span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentstack-1?view=net-9.0">"ConcurrentStack Class (System.Collections.Concurrent)"</a>. <i>learn.microsoft.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">26 November</span> 2024</span>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://doc.rust-lang.org/book/ch16-03-shared-state.html">"Shared-State Concurrency - The Rust Programming Language"</a>. <i>doc.rust-lang.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">26 November</span> 2024</span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><a href="Nancy_Lynch" title="Nancy Lynch">Nancy Lynch</a> "Distributed Computing"</li>

<li><a href="Hagit_Attiya" title="Hagit Attiya">Hagit Attiya</a> and Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"</li>

<li><a href="Doug_Lea" title="Doug Lea">Doug Lea</a>, "Concurrent Programming in Java: Design Principles and Patterns"</li>

<li><a href="Maurice_Herlihy" title="Maurice Herlihy">Maurice Herlihy</a> and <a href="Nir_Shavit" title="Nir Shavit">Nir Shavit</a>, "The Art of Multiprocessor Programming"</li>

<li>Mattson, Sanders, and Massingil "Patterns for Parallel Programming"</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303215946/http://www.ibm.com/developerworks/aix/library/au-multithreaded_structures1/index.html">Multithreaded data structures for parallel computing, Part 1</a> (Designing concurrent data structures) by Arpan Sen</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304000118/http://www.ibm.com/developerworks/aix/library/au-multithreaded_structures2/index.html">Multithreaded data structures for parallel computing: Part 2</a> (Designing concurrent data structures without mutexes) by Arpan Sen</li>

<li><a rel="nofollow" class="external text" href="https://libcds.sourceforge.net/">libcds</a> – C++ library of lock-free containers and safe memory reclamation schema</li>

<li><a rel="nofollow" class="external text" href="https://sites.google.com/site/synchrobench/">Synchrobench</a> – C/C++ and Java libraries and benchmarks of lock-free, lock-based, TM-based and RCU/COW-based data structures.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Concurrent_computing233" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Concurrent_computing233" style="font-size:114%;margin:0 4em"><a href="Concurrent_computing" title="Concurrent computing">Concurrent computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li>

<li><a href="Concurrency_control" title="Concurrency control">Concurrency control</a></li>

<li>

<ul><li><a href="Concurrent_hash_table" title="Concurrent hash table">Concurrent hash tables</a></li></ul></li>

<li><a href="Concurrent_user" title="Concurrent user">Concurrent users</a></li>

<li><a href="Indeterminacy_in_concurrent_computation" title="Indeterminacy in concurrent computation">Indeterminacy</a></li>

<li><a href="Linearizability" title="Linearizability">Linearizability</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Process_calculus" title="Process calculus">Process calculi</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Language_Of_Temporal_Ordering_Specification" class="mw-redirect" title="Language Of Temporal Ordering Specification">LOTOS</a></li>

<li><a href="%CE%A0-calculus" title="Π-calculus">π-calculus</a></li>

<li><a href="Ambient_calculus" title="Ambient calculus">Ambient calculus</a></li>

<li><a href="API-Calculus" title="API-Calculus">API-Calculus</a></li>

<li><a href="Join-calculus" title="Join-calculus">Join-calculus</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Classic problems</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="ABA_problem" title="ABA problem">ABA problem</a></li>

<li><a href="Cigarette_smokers_problem" title="Cigarette smokers problem">Cigarette smokers problem</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Dining_philosophers_problem" title="Dining philosophers problem">Dining philosophers problem</a></li>

<li><a href="Producer%E2%80%93consumer_problem" title="Producer–consumer problem">Producer–consumer problem</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Readers%E2%80%93writers_problem" title="Readers–writers problem">Readers–writers problem</a></li>

<li><a href="Sleeping_barber_problem" title="Sleeping barber problem">Sleeping barber problem</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Concurrent computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-10" href="https://en.wikipedia.org/wiki/?title=Concurrent_data_structure&oldid=1268544534">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>